原始题目:剑指 Offer 32 - II. 从上到下打印二叉树 II (opens new window)
解题思路:
层序遍历,每一层都用一个列表存放起来。
代码:
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new LinkedList<>();
Deque<TreeNode> queue = new LinkedList<>();
if(root != null) {
queue.offer(root);
}
while(!queue.isEmpty()) {
int size = queue.size();
List<Integer> list = new ArrayList<>(size);
for(int i = 0; i < size; i++) {
TreeNode node = queue.poll();
list.add(node.val);
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
ans.add(list);
}
return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
复杂度分析
- 时间复杂度: 为二叉树的节点总数。
- 空间复杂度:最差情况下,即当树为平衡二叉树时,最多有 个树节点同时在
queue
中,使用 大小的额外空间。